package com.mid;

import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

/**
 * Created by Lxk on 2020/2/3.
 */
public class Solution22 {

    private Stack<Character> stack = new Stack<>();

    private List<String> res = new ArrayList<>();

    private boolean checkRes() {
        Stack<Character> help = new Stack<>();
        for (int i = 0; i < stack.size(); i++) {
            Character ch = stack.get(i);
            if (ch == '(') {
                help.push(ch);
            } else {
                if (help.size() > 0 && '(' == help.peek()) {
                    help.pop();
                } else {
                    help.push(ch);
                }
            }
        }
        return help.isEmpty();
    }

    private void findStr(int pos, int limit) {
        if (pos >= limit) {
            if (checkRes()) {
                StringBuffer sb = new StringBuffer();
                for (int i = 0; i < stack.size(); i++) {
                    sb.append(stack.get(i));
                }
                res.add(sb.toString());
            }
            return;
        }
        stack.push('(');
        findStr(pos + 1, limit);
        stack.pop();
        stack.push(')');
        findStr(pos + 1, limit);
        stack.pop();
    }

    public List<String> generateParenthesis(int n) {
        findStr(0, 2 * n);
        return res;
    }

    public static void main(String[] args) {
        Solution22 solution22 = new Solution22();
        System.out.println(solution22.generateParenthesis(3));
    }

}
